import java.util.Random;

public class Leetcode {
}

//leetcode:75:颜色二划分
class Solution1 {
    public void sortColors(int[] nums) {
        //利用分治法将数组分成三段
        //利用三指针
        int l = 0;
        int r = nums.length-1;
        int m = 0;
        while(l <= r){
            if(nums[l] == 0){//将数组值为0的元素放到放到数组左边
                swap(nums,l++,m++);
            }else if(nums[l] == 2){//将数组值为2的元素放到放到数组右边
                swap(nums,l,r--);
            }else{//中间的元素全为1
                l++;
            }
        }
    }

    public void swap(int[] nums,int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}

//leetcode:912:排序数组
//快速选择排序算法
class Solution2 {
    public int[] sortArray(int[] nums) {
        quick(nums,0,nums.length-1);
        return nums;
    }

    public void quick(int[] nums, int start, int end) {
        if(start >= end){
            return;
        }

        //获取一个随机值key作为基准元素
        int key = nums[new Random().nextInt(end - start + 1)+start];
        int left = start,right = end;
        int i = start;
        while(i <= right){
            if(nums[i] < key ){//将小于key的值放到数组左边
                swap(nums,left++,i++);
            }else if(nums[i] > key){//将大于key的值放到数组右边
                swap(nums,right--,i);
            }else{//中间的元素全为key
                i++;
            }
        }
        quick(nums,start,left-1);
        quick(nums,right+1, end);
    }

    public void swap(int[] nums,int left,int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

//leetcode:215:数组中的第k个最大数
class Solution3 {
    public int findKthLargest(int[] nums, int k) {
        return quicksort(nums,0,nums.length-1,k);
    }

    public int quicksort(int[] nums,int start,int end,int k){
        if( start >= end){
            return nums[start];
        }
        //跟上面一样为快速选择排序算法
        int key = nums[new Random().nextInt(end - start +1)+start];
        int left = start,right = end,i = start;
        while(i <= right){
            if(nums[i] < key) swap(nums,left++,i++);
            else if(nums[i] > key) swap(nums,right--,i);
            else i++;
        }
        //根据我们可落在不同的区间进行返回
        int b = right - left + 1,c = end - right;
        if(c >= k) return quicksort(nums,right+1,end,k);//如果落在c区间返回这个区间的第k大元素
        else if(b+c >= k) return key;//如果落在b区间。直接返回key
        else return quicksort(nums,start,left-1,k-b-c);//如果落在a区间，就在a区间找第k-b-c大的元素，因为落在了a区间就要让k减去b和c区间的长度此时的到的值就是k在a区间的位置
    }

    public void swap(int[] nums,int left ,int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

//leetcode:面试题17.14.最小k个数
//同理和上面一样只是变成了找第k最小数，然后返回前k个最小数
class Solution4 {
    public int[] smallestK(int[] arr, int k) {
        quicksort(arr,0,arr.length-1,k);
        int[] num = new int[k];
        for(int i = 0;i < k;i++){
            num[i] = arr[i];
        }
        return num;
    }

    public void quicksort(int[] arr,int start,int end,int k) {
        if(start >= end){
            return;
        }
        int key = arr[new Random().nextInt(end - start +1) + start];
        int left = start,right = end ,i = start;
        while(i <= right){
            if(arr[i] < key) swap(arr,left++,i++);
            else if(arr[i] > key) swap(arr,right--,i);
            else i++;
        }
        int a = left - start ,b = right - left +1;
        if(a >= k)  quicksort(arr,start,left-1,k);
        else if(a+b >= k) return ;
        else  quicksort(arr,right+1,end,k-b-a);
    }

    public void swap(int[] nums,int left ,int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}